package Phase1.TableDFABuilder;

import Phase1.NFAHandler.NFA;
import Phase1.NFAHandler.NFANode;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: Alvin
 * Date: 11/13/12
 * Time: 4:27 PM
 * To change this template use File | Settings | File Templates.
 */
public class NFAtoDFAConverter {
    public static NFASetNode ConvertNFAtoDFA(NFA nfa) {
        HashSet<NFANode> temp = new HashSet<NFANode>();
        temp.add(nfa.head);
        HashSet<NFANode> closed = GenerateEpsilonClosureSet(temp);
        NFASetNode head = new NFASetNode();
        head.nodes = closed;
        ArrayList<NFASetNode> processedNFASetNodes = new ArrayList<NFASetNode>();
        ArrayList<NFASetNode> pendingNFASetNodes = new ArrayList<NFASetNode>();
        pendingNFASetNodes.add(head);
        while(!pendingNFASetNodes.isEmpty()) {
            NFASetNode currentNFASetNode = pendingNFASetNodes.remove(0);
            processedNFASetNodes.add(currentNFASetNode);

            HashSet<NFANode> currentNodeList = currentNFASetNode.nodes;
            ArrayList<String> transitions = GetAllValidTransitions(currentNodeList);
            for(String trans : transitions) {
                HashSet<NFANode> childNodeList = GenerateTransitionSet(currentNodeList, trans);
                if(SetContains(processedNFASetNodes, childNodeList)) {
                    currentNFASetNode.transitions.put(trans,GetMatchingSet(processedNFASetNodes,childNodeList));
                }
                else {
                    NFASetNode newNode = new NFASetNode();
                    newNode.nodes = childNodeList;
                    currentNFASetNode.transitions.put(trans,newNode);
                    pendingNFASetNodes.add(newNode);
                }
            }
        }
        return head;
    }

    public static HashSet<NFANode> GenerateEpsilonClosureSet(HashSet<NFANode> inputNodes) {
        HashSet<NFANode> output = new HashSet<NFANode>();
        output.addAll(inputNodes);
        while(true) {
            HashSet<NFANode> additionalNodes = new HashSet<NFANode>();
            for(NFANode node : output) {
                //HashMap<String,ArrayList<NFANode>> transitionList = node.transitions;
                ArrayList<NFANode> childNodes = node.transitions.get("epsilon");
                if(childNodes != null) {
                    for(NFANode child : childNodes) {
                        if(!output.contains(child) && !additionalNodes.contains(child)) {
                            additionalNodes.add(child);
                        }
                    }
                }
            }
            if(additionalNodes.isEmpty()) {
                break;
            }
            output.addAll(additionalNodes);
        }
        return output;
    }

    public static HashSet<NFANode> GenerateTransitionSet(HashSet<NFANode> inputNodes, String transition) {
        HashSet<NFANode> output = new HashSet<NFANode>();
        for(NFANode node : inputNodes) {
            ArrayList<NFANode> endStates = node.transitions.get(transition);
            if(endStates != null) {
                for(NFANode child : endStates) {
                    output.add(child);
                }
            }
        }
        return GenerateEpsilonClosureSet(output);
    }

    public static ArrayList<String> GetAllValidTransitions(HashSet<NFANode> inputNodes) {
        ArrayList<String> output = new ArrayList<String>();
        for(NFANode node : inputNodes) {
            Set<String> keyset = node.transitions.keySet();
            for(String key : keyset) {
                if(!output.contains(key) && !key.equals("epsilon")) {
                    output.add(key);
                }
            }
        }
        return output;
    }

    public static boolean SetContains(ArrayList<NFASetNode> nodes, HashSet<NFANode> set) {
        for(NFASetNode node : nodes) {
            HashSet<NFANode> children = node.nodes;
            boolean matched = true;
            for(NFANode child : children) {
                if(!set.contains(child)) {
                    matched = false;
                }
            }
            if(children.size() != set.size()) {
                matched = false;
            }
            if(matched) {
                return true;
            }
        }
        return false;
    }

    public static NFASetNode GetMatchingSet(ArrayList<NFASetNode> nodes, HashSet<NFANode> set) {
        for(NFASetNode node : nodes) {
            HashSet<NFANode> children = node.nodes;
            boolean matched = true;
            for(NFANode child : children) {
                if(!set.contains(child)) {
                    matched = false;
                }
            }
            if(children.size() != set.size()) {
                matched = false;
            }
            if(matched) {
                return node;
            }
        }
        return null;
    }
}
